package string;

import java.util.Arrays;

public class WordSearch79 {
    public boolean exist(char[][] b, String word) {
        boolean[][] v = new boolean[b.length][b[0].length];
        for (int i = 0; i < v.length; i++) {
            Arrays.fill(v[i], false);
        }
        char[] w = word.toCharArray();
        for (int i = 0; i < b.length; i++) {
            for (int j = 0; j < b[i].length; j++) {
                if (b[i][j] == w[0]) {
                    if (searchRecursively(b, v, i, j, w, 0)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public boolean searchRecursively(char[][] b, boolean[][] v, int row, int col, char[] w, int index) {
        if (v[row][col]) {
            return false;
        }
        v[row][col] = true;
        if (b[row][col] == w[index]) {
            if (index == w.length-1) {
                return true;
            } else {
                if (row > 0) {
                    if (searchRecursively(b, v, row - 1, col, w, index + 1)) {
                        return true;
                    }
                }
                if (row < b.length-1) {
                    if (searchRecursively(b, v, row + 1, col, w, index + 1)) {
                        return true;
                    }
                }
                if (col > 0) {
                    if (searchRecursively(b, v, row, col - 1, w, index + 1)) {
                        return true;
                    }
                }
                if (col < b[row].length - 1) {
                    if (searchRecursively(b, v, row, col + 1, w, index + 1)) {
                        return true;
                    }
                }
            }
        }
        v[row][col] = false;
        return false;
    }
}
